package com.daxue.code;

import org.junit.jupiter.api.Test;

/**
 * @author daxue0929
 * @date 2022/09/04
 **/
public class SearchTest {

    @Test
    public void start() {
        int[] array = new int[]{1, 12, 9, 5, 6};
         int[] result = insertSort(array);
        System.out.println(result);

//        int[] result = bubbleSort2(array);
//        System.out.println(result);

//        int[] result2 = selectSort(array);
//        System.out.println(result2);

    }


    // 3. 插入排序
    public int[] insertSort(int[] array) {
        if (array == null || array.length < 2) {
            return array;
        }
        // 你大 ，你就退一步，把你的位置空出来。让给你前面的人。
        // 没有目标值大了。此时指针已经指向了空格前面的下标，然后把目标值填到下标里
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int j = i - 1;
            while (j >= 0 && temp < array[j]) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = temp;
        }
        return array;
    }


    // 2.选择排序  每次循环都挑出来最最小的原色放在前面。
    public int[] selectSort(int[] array) {
        if (array == null || array.length < 2) {
            return array;
        }
        for (int i = 0; i < array.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            int temp;
            if (minIndex > i) {
                temp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = temp;
            }
        }
        return array;
    }


    // 1. 冒泡排序，思路把最小的弄上来。  n的平方
    public int[] bubbleSort(int[] array) {
        if (array == null || array.length < 2) {
            return array;
        }
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                int temp;
                if (array[i] > array[j]) {
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }

    // 1.1 冒泡排序, 把大的沉下去
    public int[] bubbleSort2(int[] array) {
        if (array == null || array.length < 2) {
            return array;
        }
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < array.length - 1 - i; j++) {
                int temp;
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
        return array;
    }

}
